package Algorithms;

import org.json.JSONException;
import org.json.JSONObject;
import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * 算法导论 - 最大子数组
 */
public class FindMaximumSubarray {

    /**
     * 找出跨越中心的最大子数组
     *
     * @param list 数组
     * @param low  左下标
     * @param mid  中间下标
     * @param high 右下标
     * @return {
     * 左下标，
     * 右下标，
     * 和
     * }
     */
    private JSONObject findMaxCrossSubArray(List<Integer> list, int low, int mid, int high) throws JSONException {
        //左
        int maxLeft = 0;
        int maxSumLeft = Integer.MIN_VALUE;
        int left = -1;
        for (int i = mid; i >= low; --i) {
            maxLeft += list.get(i);
            if (maxSumLeft < maxLeft) {
                maxSumLeft = maxLeft;
                left = i;
            }
        }
        //右
        int maxRight = 0;
        int maxSumRight = Integer.MIN_VALUE;
        int right = -1;
        for (int i = mid + 1; i <= high; ++i) {
            maxRight += list.get(i);
            if (maxSumRight < maxRight) {
                maxSumRight = maxRight;
                right = i;
            }
        }
        JSONObject res = new JSONObject();
        res.put("left", left);
        res.put("right", right);
        res.put("sum", maxLeft + maxRight);
        return res;
    }

    /**
     * 找出最大子数组
     */
    public JSONObject findMaximumSubarray(List<Integer> list, int low, int high) throws JSONException {
        if (low == high) {
            JSONObject res = new JSONObject();
            res.put("left", low);
            res.put("right", high);
            res.put("sum", list.get(low));
            return res;
        } else {
            int mid = (low + high) / 2;
            JSONObject leftRes = findMaximumSubarray(list, low, mid);
            JSONObject rightRes = findMaximumSubarray(list, mid + 1, high);
            JSONObject crossRes = findMaxCrossSubArray(list, low, mid, high);
            int leftSum = leftRes.getInt("sum");
            int rightSum = rightRes.getInt("sum");
            int crossSum = crossRes.getInt("sum");
            if (leftSum >= rightSum && leftSum >= crossSum) {
                return leftRes;
            } else if (leftSum <= rightSum && rightSum >= crossSum) {
                return rightRes;
            } else {
                return crossRes;
            }
        }
    }

    @Test
    public void test() throws Exception {
        List<Integer> list = Arrays.asList(4, -2, 6, -98, -2, 5, -76, 8, 54, 3, 2453465, 3, 1);
        JSONObject res = findMaximumSubarray(list, 0, list.size() - 1);
        System.out.println(res);
    }
}
